#include "common.h"

int duplicate(int* numbers, int numbersLen);

int duplicate2(int* numbers, int numbersLen);

int main()
{
	return 0;
}

int duplicate(int* numbers, int numbersLen)
{
	for (int i = 0; i < numbersLen; i++) {
		if (numbers[i] == i)
			continue;
		if (numbers[i] < i)
			return numbers[i];

		int next = numbers[i];
		while (true) {
			if (next < i)
				return numbers[next];
			if (numbers[next] == next)
				return next;
			int temp = numbers[next];
			numbers[next] = next;
			if (next == i)
				break;
			next = temp;
		}
	}

	return -1;
}

int duplicate2(int* numbers, int numbersLen)
{
	char* freq = malloc(sizeof(char) * numbersLen);
	memset(freq, 0, sizeof(freq));
	for (int i = 0; i < numbersLen; i++)
		if (freq[numbers[i]]++ == 1)
			return numbers[i];

	return -1;
}
